{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Longest Valid Parentheses"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: longestValidParentheses"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最长有效括号"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个只包含 <code>'('</code> 和 <code>')'</code> 的字符串，找出最长有效（格式正确且连续）括号子串的长度。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<div class=\"original__bRMd\">\n",
    "<div>\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"(()\"\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>最长有效括号子串是 \"()\"\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \")()())\"\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>最长有效括号子串是 \"()()\"\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"\"\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 <= s.length <= 3 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>s[i]</code> 为 <code>'('</code> 或 <code>')'</code></li>\n",
    "</ul>\n",
    "</div>\n",
    "</div>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [longest-valid-parentheses](https://leetcode.cn/problems/longest-valid-parentheses/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [longest-valid-parentheses](https://leetcode.cn/problems/longest-valid-parentheses/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"(()\"', '\")()())\"', '\"\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidParentheses(self, s: str) -> int:\n",
    "        \n",
    "        maxResult = 0\n",
    "        stack = [-1]\n",
    "\n",
    "        for i, c in enumerate(s):\n",
    "            if c == ')':\n",
    "                stack.pop()\n",
    "                if not stack:\n",
    "                    stack.append(i)\n",
    "                else:\n",
    "                    maxResult = max(maxResult, i - stack[-1])\n",
    "            elif c == '(':\n",
    "                stack.append(i)\n",
    "                \n",
    "        return maxResult\n",
    "          \n",
    "        \n",
    "                    \n",
    "                \n",
    "                \n",
    "                \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidParentheses(self, s: 'str') -> 'int':\n",
    "        longest = 0\n",
    "        stack = []\n",
    "        num_left = 0\n",
    "        for c in s:\n",
    "            if c == '(':\n",
    "                num_left += 1\n",
    "            else:\n",
    "                if num_left > 0:\n",
    "                    num_left -= 1\n",
    "                    if stack and stack[-1][1] == num_left:\n",
    "                        stack[-1][0] += 2\n",
    "                        longest = max(longest, stack[-1][0])\n",
    "                    elif stack and stack[-1][1] == num_left + 1:\n",
    "                        rec = [stack[-1][0] + 2, num_left]\n",
    "                        stack.pop(-1)\n",
    "                        if stack and stack[-1][1] == num_left:\n",
    "                            rec = [rec[0] + stack[-1][0], num_left]\n",
    "                            stack.pop(-1)\n",
    "                        stack.append(rec)\n",
    "                        longest = max(longest, stack[-1][0])\n",
    "                    else:\n",
    "                        stack.append([2, num_left])\n",
    "                        longest = max(longest, 2)\n",
    "                else:\n",
    "                    stack = []\n",
    "            # print(stack)\n",
    "\n",
    "        # print(longest)\n",
    "        return longest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidParentheses(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if len(s) == 0:\n",
    "            return 0\n",
    "        dp = [0] * len(s)\n",
    "        max_ = 0\n",
    "        for i in range(1,len(s)):\n",
    "            if s[i] == ')':\n",
    "                if s[i-1] == '(':\n",
    "                    if i-2>=0:\n",
    "                        dp[i] = dp[i-2]+ 2\n",
    "                    else:\n",
    "                        dp[i] = 2\n",
    "                else:\n",
    "                    if i-dp[i-1]-1 >= 0 and s[i-dp[i-1]-1] == '(':\n",
    "                        if i-dp[i-1]-2>=0:\n",
    "                            dp[i] = dp[i-1] + dp[i-dp[i-1]-2] + 2\n",
    "                        else:\n",
    "                            dp[i] = dp[i-1] + 2\n",
    "                max_ = max(max_,dp[i])\n",
    "        return max_    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def longestValidParentheses(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        lenS = len(s)\n",
    "        if not s: return 0\n",
    "\n",
    "        def findLeft(start):\n",
    "            if start >= lenS: return 0\n",
    "            leftMax = 0\n",
    "\n",
    "            while start < lenS and s[start] is not '(':\n",
    "                start += 1\n",
    "            end, left, right = start, 0, 0\n",
    "            while end < lenS and left >= right:\n",
    "                if s[end] is ')':\n",
    "                    right += 1\n",
    "                else:\n",
    "                    left += 1\n",
    "                if left == right:\n",
    "                    leftMax = max(leftMax, 2*left)\n",
    "                end += 1\n",
    "            return max(leftMax, findLeft(end))\n",
    "\n",
    "        def findRight(start):\n",
    "            if start <= 0: return 0\n",
    "            rightMax = 0\n",
    "\n",
    "            while start >= 0 and s[start] is not ')':\n",
    "                start -= 1\n",
    "            end, left, right = start, 0, 0\n",
    "            while end >= 0 and right >= left:\n",
    "                if s[end] is ')':\n",
    "                    right += 1\n",
    "                else:\n",
    "                    left += 1\n",
    "                if left == right:\n",
    "                    rightMax = max(rightMax, 2*left)\n",
    "                end -= 1\n",
    "            return max(rightMax, findRight(end))\n",
    "        \n",
    "        return max(findLeft(0), findRight(lenS-1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidParentheses(self, s):\n",
    "        stack = []\n",
    "        i, len_ = 0, len(s)\n",
    "\n",
    "        while i < len_:\n",
    "            if s[i] == ')':\n",
    "                if len(stack) == 0:\n",
    "                    stack.append(i)\n",
    "                else:\n",
    "                    if s[stack[-1]] == '(':\n",
    "                        stack.pop()\n",
    "                    else:\n",
    "                        stack.append(i)\n",
    "                i += 1\n",
    "            else:\n",
    "                stack.append(i)\n",
    "                i += 1\n",
    "\n",
    "        a, b = len_, 0\n",
    "        max_ = 0\n",
    "        if stack == []:\n",
    "            return a\n",
    "\n",
    "        while stack != []:\n",
    "            b = stack.pop()\n",
    "            max_ = max(max_, a-b-1)\n",
    "            a = b\n",
    "\n",
    "        return max(max_, a)\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidParentheses(self, s):\n",
    "        s = ')' + s\n",
    "        n = len(s)\n",
    "        if n<2:\n",
    "            return 0\n",
    "        ans = 0\n",
    "        \n",
    "        dp = [0] * n\n",
    "        \n",
    "        for i in range(1,n):\n",
    "            if s[i] == ')':\n",
    "                if s[i-1-dp[i-1]] == '(':\n",
    "                    dp[i] = dp[i - 1] + 2\n",
    "                dp[i] += dp[i-dp[i]]\n",
    "            ans = max(ans,dp[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def longestValidParentheses(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        s = ')' + s\n",
    "        r1 = [')',]\n",
    "        r2 = [0,]\n",
    "        for i in s[1:] :\n",
    "            if i == '(':\n",
    "                r1.append('(')\n",
    "                r2.append(0)\n",
    "                #print('1:  ',r1,r2)\n",
    "            else:\n",
    "                if r1[-1] == '(':\n",
    "                    r1.pop()\n",
    "                    r2[-2] += (2 + r2[-1])\n",
    "                    r2.pop()\n",
    "                    #print('2:  ',r1,r2)\n",
    "                else:\n",
    "                    r1.append(')')\n",
    "                    r2.append(0)\n",
    "                    #print('3:  ',r1,r2)\n",
    "        return max(r2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidParentheses(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if len(s) == 0:\n",
    "            return 0\n",
    "        dp = [0] * len(s)\n",
    "        max_ = 0\n",
    "        for i in range(1,len(s)):\n",
    "            if s[i] == ')':\n",
    "                if s[i-1] == '(':\n",
    "                    if i-2>=0:\n",
    "                        dp[i] = dp[i-2]+ 2\n",
    "                    else:\n",
    "                        dp[i] = 2\n",
    "                else:\n",
    "                    if i-dp[i-1]-1 >= 0 and s[i-dp[i-1]-1] == '(':\n",
    "                        if i-dp[i-1]-2>=0:\n",
    "                            dp[i] = dp[i-1] + dp[i-dp[i-1]-2] + 2\n",
    "                        else:\n",
    "                            dp[i] = dp[i-1] + 2\n",
    "                max_ = max(max_,dp[i])\n",
    "        # print(dp)\n",
    "        return max_  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidParentheses(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        stack = []\n",
    "        maxLength = {}   # (k, v)表示以第k位结尾的最长的有效括号长度是v\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == '(':\n",
    "                stack.append(i)\n",
    "            else:\n",
    "                if len(stack) == 0: continue\n",
    "                index = stack.pop()  # 对应的左括号的index\n",
    "                print(index)\n",
    "                if index - 1 in maxLength:\n",
    "                    maxLength[i] = maxLength[index - 1] + i - index + 1\n",
    "                else:\n",
    "                    maxLength[i] = i - index + 1\n",
    "             \n",
    "        if len(maxLength) == 0: \n",
    "            return 0\n",
    "        else:\n",
    "            return max(maxLength.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidParentheses(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        stack = []\n",
    "        last = -1 \n",
    "        max_len = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] ==\"(\":\n",
    "                stack.append(i)\n",
    "            else:\n",
    "                if len(stack) == 0:\n",
    "                    last = i\n",
    "                else:\n",
    "                    stack.pop()\n",
    "                    if len(stack) == 0:\n",
    "                        max_len = max(max_len, i - last)\n",
    "                    else:\n",
    "                        max_len = max(max_len, i - stack[-1])\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def longestValidParentheses(self, s):\n",
    "\n",
    "        lenS = len(s)\n",
    "        if not s: return 0\n",
    "        \n",
    "        stack, maxLen, leftMinusRight = [-1], 0, 0\n",
    "        for i in range(lenS):\n",
    "          \n",
    "            if leftMinusRight is 0 and s[i] is ')':\n",
    "                stack[-1] = i\n",
    "                continue\n",
    "            if s[i] is '(':\n",
    "                leftMinusRight += 1\n",
    "                stack.append(i)\n",
    "            else:\n",
    "                leftMinusRight -= 1\n",
    "                stack.pop()\n",
    "                maxLen = max(maxLen, i - stack[-1])\n",
    "        \n",
    "        return maxLen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\n",
    "# @lc app=leetcode.cn id=32 lang=python3\n",
    "#\n",
    "# [32] 最长有效括号\n",
    "#\n",
    "# https://leetcode-cn.com/problems/longest-valid-parentheses/description/\n",
    "#\n",
    "# algorithms\n",
    "# Hard (25.02%)\n",
    "# Total Accepted:    6.4K\n",
    "# Total Submissions: 25.4K\n",
    "# Testcase Example:  '\"(()\"'\n",
    "#\n",
    "# 给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。\n",
    "#\n",
    "# 示例 1:\n",
    "#\n",
    "# 输入: \"(()\"\n",
    "# 输出: 2\n",
    "# 解释: 最长有效括号子串为 \"()\"\n",
    "#\n",
    "#\n",
    "# 示例 2:\n",
    "#\n",
    "# 输入: \")()())\"\n",
    "# 输出: 4\n",
    "# 解释: 最长有效括号子串为 \"()()\"\n",
    "#\n",
    "#\n",
    "#\n",
    "class Solution:\n",
    "    def longestValidParentheses(self, s: 'str') -> 'int':\n",
    "        if len(s) < 2:\n",
    "            return 0\n",
    "\n",
    "        stack = []\n",
    "        n = []\n",
    "        for i, c in enumerate(s):\n",
    "            if c == '(' and len(stack) == 0:\n",
    "                stack.append((c, i))\n",
    "            elif c == '(' and stack[-1][0] == '(':\n",
    "                stack.append((c, i))\n",
    "            elif c == '(' and stack[-1][0] == ')':\n",
    "                stack.append((c, i))\n",
    "            elif c == ')' and len(stack) == 0:\n",
    "                stack.append((c, i))\n",
    "            elif c == ')' and stack[-1][0] == '(':\n",
    "                #reduce\n",
    "                left = stack.pop()\n",
    "                left = left[1]\n",
    "                right = i\n",
    "                while True:\n",
    "                    if len(n) == 0:\n",
    "                        break\n",
    "\n",
    "                    if n[-1][0] > left:\n",
    "                        n.pop()\n",
    "                    elif n[-1][1] + 1 == left:\n",
    "                        left = n[-1][0]\n",
    "                        n.pop()\n",
    "                    else:\n",
    "                        break\n",
    "\n",
    "                n.append((left, right))\n",
    "\n",
    "            elif c == ')' and stack[-1][0] == ')':\n",
    "                #error\n",
    "                stack.append((c, i))\n",
    "            else:\n",
    "                raise RuntimeError('unkown')\n",
    "\n",
    "        m = 0\n",
    "        for left, right in n:\n",
    "            if right - left + 1 > m:\n",
    "                m = right - left + 1\n",
    "        return m\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    print(Solution().longestValidParentheses('()(())'))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidParentheses(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        lens_lis = [0]\n",
    "        for i in range(1, len(s), 1):\n",
    "            if s[i] == \"(\":\n",
    "                lens_lis.append(0)\n",
    "            elif s[i] == \")\":\n",
    "                if s[i-1] == \"(\":\n",
    "                    lens_lis.append(2 if i<=1 else lens_lis[i - 2] + 2)\n",
    "                else:\n",
    "                    if i - lens_lis[i-1] > 0 and s[i-lens_lis[i-1] -1] == \"(\":\n",
    "                        lens_lis.append((lens_lis[i - 1] + lens_lis[i - lens_lis[i - 1] - 2] + 2)  if i - lens_lis[i - 1] - 2>=0 else (lens_lis[i - 1] + 2))\n",
    "                    else:\n",
    "                        lens_lis.append(0)\n",
    "\n",
    "        print(lens_lis)\n",
    "        return max(lens_lis)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidParentheses(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not s or len(s)==0:\n",
    "            return 0\n",
    "        stack = []\n",
    "        for i,p in enumerate(s):\n",
    "            if p=='(':\n",
    "                stack.append((i,p))\n",
    "            else:\n",
    "                if stack and stack[-1][1]=='(':\n",
    "                    stack.pop()\n",
    "                else:\n",
    "                    stack.append((i,p))\n",
    "        if not stack:\n",
    "            return len(s)\n",
    "        nums = [-1]+[i for (i,p) in stack]+[len(s)]\n",
    "        i = t = 0\n",
    "        while i+1<len(nums):\n",
    "            t =max(t,nums[i+1]-nums[i]-1)\n",
    "            i+=1\n",
    "        return t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def longestValidParentheses(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        len_s = len(s)\n",
    "        if len_s == 0: return 0\n",
    "        stack = []\n",
    "        longest_flag = [False for x in range(len_s)]\n",
    "        longest = 0\n",
    "\n",
    "        for i in range(len_s):\n",
    "            if s[i] =='(':\n",
    "                stack.append([s[i], i])\n",
    "            elif s[i] ==')':\n",
    "                if len(stack) != 0:\n",
    "                    stacktemp = stack.pop()\n",
    "                    if stacktemp[0] == '(':\n",
    "                        longest_flag[stacktemp[1]] = True\n",
    "                        longest_flag[i] = True\n",
    "\n",
    "        temp = 0\n",
    "        i  = 0\n",
    "        while i < len_s:\n",
    "            # print(s[i])\n",
    "            if longest_flag[i]:\n",
    "                temp += 1\n",
    "                longest = max(longest, temp)\n",
    "            else:\n",
    "                temp = 0\n",
    "            i += 1\n",
    "        return longest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidParentheses(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        ns = []\n",
    "        for i in s:\n",
    "            if i == '(':\n",
    "                ns.append(1)\n",
    "            else:\n",
    "                ns.append(-1)\n",
    "        #print(ns)\n",
    "        maxl = 0\n",
    "        sums = {0: -1}\n",
    "        sumi = 0\n",
    "        for i in range(len(ns)):\n",
    "            sumi += ns[i]\n",
    "            if ns[i] == -1 and sumi in sums:\n",
    "                maxl = max(maxl, i-sums[sumi])\n",
    "                #print(i-sums[sumi]+1)\n",
    "            if ns[i] == 1 or sumi not in sums:\n",
    "                sums[sumi] = i\n",
    "            #print(sumi, sums, maxl)\n",
    "                \n",
    "        return maxl"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidParentheses(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        stack=['#']\n",
    "        res=0\n",
    "        index=['0']*len(s)\n",
    "        for i,x in enumerate(s):\n",
    "            if x==')':\n",
    "                li=stack.pop()\n",
    "                if li[0]=='(': \n",
    "                    index[i]='1'\n",
    "                    index[li[1]]='1'        \n",
    "                else:\n",
    "                    stack=['#']         \n",
    "            else:\n",
    "                stack.append(['(',i])\n",
    "                \n",
    "        lenlist=''.join(index)\n",
    "        lenlist=lenlist.split('0')\n",
    "        for i in lenlist:\n",
    "            l=len(i)\n",
    "            if l>res:\n",
    "                res=l\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidParentheses(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        stack = []\n",
    "        idx = 0\n",
    "        l = len(s)\n",
    "        result = [0]*l\n",
    "        i = -1\n",
    "        while idx < l:\n",
    "            while idx < l and self.is_val(s[idx], stack,i): \n",
    "                if s[idx] == '(':\n",
    "                    stack.append(['(',idx])\n",
    "                    i = i + 1\n",
    "                else:\n",
    "                    result[idx] = 1\n",
    "                    result[stack[-1][1]]=1\n",
    "                    stack.pop(-1)\n",
    "                    i = i - 1\n",
    "                idx = idx + 1\n",
    "            if idx < l and self.is_val(s[idx],stack,i) == False:\n",
    "                stack = []\n",
    "                i = -1\n",
    "                idx = idx + 1\n",
    "        m = 0\n",
    "        print(result)\n",
    "        for i in range(len(result)):\n",
    "            if i == 0 or result[i] == 0:\n",
    "                continue\n",
    "            result[i] = result[i-1] + result[i]\n",
    "            m = max(m, result[i])\n",
    "        print(result)\n",
    "        return m\n",
    "       \n",
    "                \n",
    "    def is_val(self,ch,stack,i):\n",
    "        if ch == '(':\n",
    "            return True\n",
    "        if ch == ')' and i > -1:\n",
    "            if stack[i][0] == '(':\n",
    "                return True\n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidParentheses(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        list_ = []\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == ')' and len(list_) != 0 and list_[-1][0] == '(':\n",
    "                list_.pop()\n",
    "            else:\n",
    "                list_.append([s[i], i])\n",
    "        print(list_)\n",
    "        list_.insert(0, ['(', -1])\n",
    "        list_.append(['(', len(s)])\n",
    "        result = 0\n",
    "        for i in range(len(list_) - 1):\n",
    "            result = max(result, list_[i + 1][1] - list_[i][1] - 1)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidParentheses(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        class DLNode:\n",
    "            def __init__(self, v):\n",
    "                self.v = v\n",
    "                self.p = None\n",
    "                self.n = None\n",
    "        dm = DLNode(')')\n",
    "        cur = dm\n",
    "        for c in s + '(':\n",
    "            cur.n = DLNode(c)\n",
    "            cur.n.p = cur\n",
    "            cur = cur.n\n",
    "        cur = dm.n\n",
    "        while cur:\n",
    "            if cur.v == '(':\n",
    "                if cur.n and cur.n.v == ')':\n",
    "                    cur.v = 2\n",
    "                    cur.n = cur.n.n\n",
    "                    cur.n.p = cur\n",
    "                    continue\n",
    "            elif cur.v == ')':\n",
    "                if cur.p and cur.p.v == '(':\n",
    "                    cur.v = 2\n",
    "                    cur.p = cur.p.p\n",
    "                    cur.p.n = cur\n",
    "                    continue\n",
    "            else:\n",
    "                if cur.n and cur.n.v != '(' and cur.n.v != ')':\n",
    "                    cur.v += cur.n.v\n",
    "                    cur.n = cur.n.n\n",
    "                    cur.n.p = cur\n",
    "                    continue\n",
    "                elif cur.p and cur.p.v != '(' and cur.p.v != ')':\n",
    "                    cur.v += cur.p.v\n",
    "                    cur.p = cur.p.p\n",
    "                    cur.p.n = cur\n",
    "                    continue\n",
    "                elif cur.p and cur.n and cur.p.v == '(' and cur.n.v == ')':\n",
    "                    cur.p.v = 2 + cur.v\n",
    "                    cur = cur.p\n",
    "                    cur.n=cur.n.n.n\n",
    "                    cur.n.p = cur\n",
    "                    continue\n",
    "            cur = cur.n\n",
    "        cur = dm\n",
    "        res = 0\n",
    "        while cur:\n",
    "            if cur.v != '(' and cur.v != ')':\n",
    "                res = max(res, cur.v)\n",
    "            cur = cur.n\n",
    "        return res\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def longestValidParentheses(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        len_s = len(s)\n",
    "        if len_s == 0: return 0\n",
    "        stack = []\n",
    "        longest_flag = [False for x in range(len_s)]\n",
    "        longest = 0\n",
    "\n",
    "        for i in range(len_s):\n",
    "            if s[i] =='(':\n",
    "                stack.append([s[i], i])\n",
    "            elif s[i] ==')':\n",
    "                if len(stack) != 0:\n",
    "                    stacktemp = stack.pop()\n",
    "                    if stacktemp[0] == '(':\n",
    "                        longest_flag[stacktemp[1]] = True\n",
    "                        longest_flag[i] = True\n",
    "\n",
    "        temp = 0\n",
    "        i  = 0\n",
    "        while i < len_s:\n",
    "            print(s[i])\n",
    "            if longest_flag[i]:\n",
    "                temp += 1\n",
    "                longest = max(longest, temp)\n",
    "            else:\n",
    "                temp = 0\n",
    "            i += 1\n",
    "        return longest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidParentheses(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        ss = list(s)\n",
    "        s = [[ss[i],i] for i in range(len(s))]\n",
    "        temp = [0 for i in range(len(s))]\n",
    "        i = 1\n",
    "        while i < len(s):\n",
    "            if s[i - 1][0] == \"(\" and s[i][0] == \")\":\n",
    "                temp[s[i-1][1]] = 1\n",
    "                temp[s[i][1]] = 1\n",
    "                s.pop(i - 1)\n",
    "                s.pop(i - 1)\n",
    "                i = max(1, i - 1)\n",
    "            else:\n",
    "                i+=1\n",
    "\n",
    "        max_ = 0\n",
    "        cur = 0\n",
    "        temp.append(0)\n",
    "        for i in temp:\n",
    "            if i == 1:\n",
    "                cur += 1\n",
    "            if i == 0 and cur != 0:\n",
    "                max_ = max(max_,cur)\n",
    "                cur = 0\n",
    "        return max_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidParentheses(self, s: 'str') -> 'int':\n",
    "        n = len(s)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        left = 0\n",
    "        right = 0\n",
    "        i = 0\n",
    "        maxi = 0\n",
    "        while i < n:\n",
    "            if s[i] == '(':\n",
    "                left += 1\n",
    "            else:\n",
    "                right += 1\n",
    "            if left == right:\n",
    "                if maxi < 2 * left:\n",
    "                    maxi = 2 * left\n",
    "            elif left < right:\n",
    "                left = 0\n",
    "                right = 0\n",
    "            i += 1\n",
    "        i = n - 1\n",
    "        left = 0\n",
    "        right = 0\n",
    "        while i >= 0:\n",
    "            if s[i] == '(':\n",
    "                left += 1\n",
    "            else:\n",
    "                right += 1\n",
    "            if left == right:\n",
    "                if maxi < 2 * left:\n",
    "                    maxi = 2 * left\n",
    "            elif left > right:\n",
    "                left = 0\n",
    "                right = 0\n",
    "            i -= 1\n",
    "        return maxi\n",
    "        \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidParentheses(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        if n == 0: return 0\n",
    "        dp = [0] * n\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if i>0 and s[i] == \")\":\n",
    "                if  s[i - 1] == \"(\":\n",
    "                    dp[i] = dp[i - 2] + 2\n",
    "                elif s[i - 1] == \")\" and i - dp[i - 1] - 1 >= 0 and s[i - dp[i - 1] - 1] == \"(\":\n",
    "                    dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2]\n",
    "                if dp[i] > res:\n",
    "                    res = dp[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidParentheses(self, s: str) -> int:\n",
    "        maxans = 0\n",
    "        dp = [0] * len(s)\n",
    "        for k in range(1, len(s)):\n",
    "            if s[k] == ')':\n",
    "                if s[k-1] == '(':\n",
    "                    if k-2 >= 0:\n",
    "                        dp[k] = dp[k-2] + 2\n",
    "                    else:\n",
    "                        dp[k] = 0 + 2\n",
    "                elif k-dp[k-1]-1 >= 0 and s[k-dp[k-1]-1] == '(':\n",
    "                    if k-dp[k-1]-2 >= 0:\n",
    "                        dp[k] = dp[k-1] + dp[k-dp[k-1]-2] + 2\n",
    "                    else:\n",
    "                        dp[k] = dp[k-1] + 0 + 2\n",
    "                maxans = max(maxans, dp[k])\n",
    "        return maxans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidParentheses(self, s: str) -> int:\n",
    "        length = len(s)\n",
    "        if length < 2:\n",
    "            return 0\n",
    "        dp = [0 for _ in range(length)]\n",
    "        max_length = 0\n",
    "        for i in range(1,length):\n",
    "            if s[i] is ')' and s[i-1] is '(':\n",
    "                dp[i] = dp[i-2]+2\n",
    "            if s[i] is ')' and s[i-1] is ')':\n",
    "                if i-dp[i-1]-1 >=0:\n",
    "                    if s[i-dp[i-1]-1] is '(':\n",
    "                        if i-dp[i-1]-2>=0:\n",
    "                            dp[i] = dp[i-1]+dp[i-dp[i-1]-2]+2\n",
    "                        else:\n",
    "                            dp[i] = dp[i-1]+2\n",
    "            max_length = max(max_length,dp[i])\n",
    "        return max_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidParentheses(self, s: str) -> int:\n",
    "        # 使用栈\n",
    "        \n",
    "#         stack = []\n",
    "#         cnt = 0\n",
    "        \n",
    "#         for i in range(len(s)):\n",
    "#             if s[i] == '(':\n",
    "#                 stack.append('(')\n",
    "#             else:\n",
    "#                 if len(stack) > 0:\n",
    "#                     stack.pop()\n",
    "#                     cnt += 1\n",
    "#         return cnt * 2\n",
    "        # 使用动态规划\n",
    "        # dp[i] 表示以i结尾的 最长有效括号长度\n",
    "        n = len(s)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        \n",
    "        dp = [0] * n\n",
    "        res = 0\n",
    "        for i in range(1, n):\n",
    "            if s[i] == ')':\n",
    "                if s[i-1] == '(':\n",
    "                    dp[i] = dp[i-2] + 2\n",
    "                else:\n",
    "                    if i-1-dp[i-1] >=0 and s[i-1-dp[i-1]] == '(':\n",
    "                        dp[i] = 2 + dp[i-1] + dp[i-2-dp[i-1]]\n",
    "            if dp[i] > res:\n",
    "                res = dp[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidParentheses(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        if n <= 1:\n",
    "            return 0\n",
    "        f = [0 for _ in range(n)]\n",
    "        ans = 0\n",
    "        for i in range(1, n):\n",
    "            if s[i] == '(':\n",
    "                continue\n",
    "            if s[i] == ')':\n",
    "                if s[i-1] == '(':\n",
    "                    f[i] = f[i-2] + 2\n",
    "                elif s[i-1] == ')':\n",
    "                    j = i - f[i-1] - 1\n",
    "                    if j >= 0 and s[j] == '(':\n",
    "                        f[i] = f[i-1] + 2 if j <= 0 else f[j-1] + f[i-1] + 2\n",
    "            ans = max(ans, f[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidParentheses(self, s: str) -> int:\n",
    "        \"\"\"\n",
    "        分析：子串&最长有效括号&长度\n",
    "        思路：一直搜集左括号，在左括号不为0之前，一直与右括号配对，当前左括号为0，下一个为右括号时，直接在下一个右括号后面开始，一直到结束，时空复杂度： O(n)\\O(n),堆栈的方法？\n",
    "        思路2: (这样的做法贪心地考虑了以当前字符下标结尾的有效括号长度，每次当右括号数量多于左括号数量的时候之前的字符我们都扔掉不再考虑，重新从下一个字符开始计算，但这样会漏掉一种情况，就是遍历的时候左括号的数量始终大于右括号的数量，即 (() ，这种时候最长有效括号是求不出来的。\n",
    "解决的方法也很简单，我们只需要从右往左遍历用类似的方法计算即可，只是这个时候判断条件反了过来)\n",
    "        1. 使用左右指针分别进行左右指针计数\n",
    "        2. 第一次从左到右遍历，遇到“（”时，left+1， “）”时，right+1， 如果right>left，两者设为0，重新开始，当right==left时， maxlen = max（maxlen， 2*left）\n",
    "        3. 第2次从右往左遍历，遇到“）”时，right+1， “（”时，left+1， 如果left>right, 两者设为0，继续，maxlen = max（maxlen， 2*left）\n",
    "        4. 取上述两次遍历最大值即可\n",
    "        5. 时空复杂度： O(2n)-O(n)/O(1)\n",
    "        \"\"\"\n",
    "        left, right, max_len = 0, 0, 0\n",
    "        for c in s:\n",
    "            if c == \"(\":\n",
    "                left += 1\n",
    "            else:\n",
    "                right += 1\n",
    "            if left == right:\n",
    "                max_len = max(max_len, 2*left)\n",
    "            if right > left:\n",
    "                left, right = 0, 0\n",
    "        # 解决(()这种情况的问题\n",
    "        left, right = 0, 0\n",
    "        n = len(s)\n",
    "        for j in range(n):\n",
    "            if s[n-j-1] == \")\":\n",
    "                right += 1\n",
    "            else:\n",
    "                left += 1\n",
    "            if right == left:\n",
    "                max_len = max(max_len, 2*right)\n",
    "            if left > right:\n",
    "                left, right = 0, 0\n",
    "        return max_len\n",
    "                \n",
    "        # n = len(s)\n",
    "        # if n == 0: return 0\n",
    "        # dp = [0] * n\n",
    "        # res = 0\n",
    "        # for i in range(n):\n",
    "        #     if i>0 and s[i] == \")\":\n",
    "        #         if  s[i - 1] == \"(\":\n",
    "        #             dp[i] = dp[i - 2] + 2\n",
    "        #         elif s[i - 1] == \")\" and i - dp[i - 1] - 1 >= 0 and s[i - dp[i - 1] - 1] == \"(\":\n",
    "        #             dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2]\n",
    "        #         if dp[i] > res:\n",
    "        #             res = dp[i]\n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidParentheses(self, s: str) -> int:\n",
    "        res = 0\n",
    "        stack = []\n",
    "        dp = [0] * len(s)\n",
    "        for i, char in enumerate(s):\n",
    "            if char == '(':\n",
    "                stack.append(2)\n",
    "            else:\n",
    "                if stack:\n",
    "                    ele = stack.pop()\n",
    "                    if stack:\n",
    "                        stack[-1] += ele\n",
    "                    dp[i] += ele\n",
    "                    if i >= ele:\n",
    "                        dp[i] += dp[i - ele]\n",
    "                    res = max(res, dp[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidParentheses(self, s: str) -> int:\n",
    "        if not s:\n",
    "            return 0\n",
    "        dp = [0] * len(s)\n",
    "        for i in range(1, len(s)):\n",
    "            if s[i] == '(':\n",
    "                continue\n",
    "            if s[i] == \")\":\n",
    "                if s[i-1] == \"(\":\n",
    "                    dp[i] = dp[i-2] + 2\n",
    "                elif s[i-1] == \")\":\n",
    "                    if i-dp[i-1]-1 >= 0 and s[i-dp[i-1]-1] == \"(\":\n",
    "                        dp[i] = dp[i-dp[i-1]-2] + dp[i-1] + 2\n",
    "        print(dp)\n",
    "        return max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidParentheses(self, s: str) -> int:\n",
    "        \n",
    "        if len(s) < 1:\n",
    "            return 0\n",
    "\n",
    "        stack = [-1]\n",
    "        ans = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == '(':\n",
    "                stack.append(i)\n",
    "            elif s[i] == ')' and stack:\n",
    "                stack.pop()\n",
    "                if not stack:\n",
    "                    stack.append(i)\n",
    "                else:\n",
    "                    ans = max(ans, i - stack[-1])\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidParentheses(self, s: str) -> int:\n",
    "        stack = []\n",
    "        maxNum = 0\n",
    "        i = 0\n",
    "        n = len(s)\n",
    "        match = [False] * len(s)  ##记录是否匹配成功\n",
    "        while i < n:\n",
    "\n",
    "            if s[i] == '(':\n",
    "                stack.append(i)\n",
    "            else:\n",
    "                if len(stack) > 0:     ##存在和')'匹配的'('\n",
    "                    match[stack.pop()] = True\n",
    "                    match[i] = True\n",
    "            i += 1\n",
    "        ###统计连续的匹配数 \n",
    "        #print(match)   \n",
    "        j = 0\n",
    "        num = 0\n",
    "        while j < n:\n",
    "            if match[j]:\n",
    "                num += 1\n",
    "            else:\n",
    "                if num > maxNum:\n",
    "                    maxNum = num\n",
    "                num = 0\n",
    "            j += 1\n",
    "        maxNum = max(num, 0, maxNum)    \n",
    "        return maxNum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidParentheses(self, s: str) -> int:\n",
    "        left = list()\n",
    "        new_s = list()\n",
    "        cnt = 0\n",
    "        longest = 0\n",
    "        for i in range(0,len(s)):\n",
    "            new_s.append(s[i])\n",
    "            if s[i] == '(':\n",
    "                left.append(i)\n",
    "            else:\n",
    "                if len(left) > 0:\n",
    "                    new_s[left[-1]]=1\n",
    "                    new_s[i]=1\n",
    "                    left.pop(-1)\n",
    "                else:\n",
    "                    pass\n",
    "        for item in new_s:\n",
    "            if item == 1:\n",
    "                cnt+=1\n",
    "                if cnt>longest:\n",
    "                    longest=cnt\n",
    "            if item != 1:\n",
    "                cnt=0\n",
    "            \n",
    "        return longest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidParentheses(self, s: str) -> int:\n",
    "        left, right, maxlen = 0, 0, 0\n",
    "        for curr in s:\n",
    "            if curr == '(':\n",
    "                left += 1\n",
    "            elif curr == ')':\n",
    "                right += 1\n",
    "            if left == right:\n",
    "                maxlen = max(maxlen, left+right)\n",
    "            elif right > left:\n",
    "                left = 0\n",
    "                right = 0\n",
    "        \n",
    "        left, right = 0, 0\n",
    "        for curr in s[::-1]:\n",
    "            if curr == '(':\n",
    "                left += 1\n",
    "            elif curr == ')':\n",
    "                right += 1\n",
    "            if left == right:\n",
    "                maxlen = max(maxlen, left+right)\n",
    "            elif left > right:\n",
    "                left = 0\n",
    "                right = 0\n",
    "        return maxlen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidParentheses(self, s: str) -> int:\n",
    "        left = right = 0\n",
    "        mx = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == '(': left += 1\n",
    "            else: right += 1\n",
    "            if left == right: mx = max(mx, 2 * left)\n",
    "            if right > left: left = right = 0\n",
    "        left = right =  0\n",
    "        for i in range(len(s) - 1, -1, -1):\n",
    "            if s[i] == '(': left += 1\n",
    "            else: right += 1\n",
    "            if left == right: mx = max(mx, 2 * left)\n",
    "            if right < left: left = right = 0\n",
    "        return mx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidParentheses(self, s: str) -> int:\n",
    "        if not s:\n",
    "            return 0\n",
    "\n",
    "        length = len(s)\n",
    "        # 用来存储每个位置的有效长度\n",
    "        dp = [0] * length\n",
    "        for i in range(length):\n",
    "            # i - dp[i-1] - 1 是当前‘）对称的位置\n",
    "            index = i - dp[i-1] - 1\n",
    "            if s[i] == ')' and index >= 0 and s[index] == '(':\n",
    "                dp[i] = dp[i-1] + dp[index - 1] + 2\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidParentheses(self, s: str) -> int:\n",
    "        if s=='':\n",
    "            return 0\n",
    "        s=list(s)\n",
    "        l=len(s)\n",
    "        dp=[0 for _ in range(l)]\n",
    "        \n",
    "        for i in range(1,l):\n",
    "            if s[i]==')':\n",
    "                left=i-dp[i-1]-1\n",
    "                if left>=0 and s[left]=='(':\n",
    "                    dp[i]=dp[i-1]+2\n",
    "                    if left>0:\n",
    "                        dp[i]+=dp[left-1]\n",
    "        return max(dp)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidParentheses(self, s: str) -> int:\n",
    "        \n",
    "        stack=[]\n",
    "        ori=0\n",
    "\n",
    "        for i in range(len(s)):\n",
    "\n",
    "            if stack and s[stack[-1]]=='(' and s[i]==')':\n",
    "                stack.pop()\n",
    "                cur = i -(stack[-1] if stack else -1)\n",
    "                ori=max(cur,ori)\n",
    "            else:\n",
    "                stack.append(i)\n",
    "\n",
    "        return ori\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidParentheses(self, s: str) -> int:\n",
    "        left = 0\n",
    "        right = 0\n",
    "        l_max = 0\n",
    "        for i in s:\n",
    "            if left < right:\n",
    "                left =0;right = 0\n",
    "            if i == '(':\n",
    "                left += 1\n",
    "            else:\n",
    "                right += 1\n",
    "            if left == right:\n",
    "                l_max = max(l_max , left + right)\n",
    "        r_max = 0\n",
    "        right = 0 ;left = 0\n",
    "        for i in s[::-1]:\n",
    "            if left > right:\n",
    "                left =0;right = 0\n",
    "            if i == '(':\n",
    "                left += 1\n",
    "            else:\n",
    "                right += 1\n",
    "            if left == right:\n",
    "                r_max = max(r_max , left + right)\n",
    "        return max(r_max,l_max)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidParentheses(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        res = 0\n",
    "        left = 0\n",
    "        right = 0\n",
    "        for i in range(n):\n",
    "            if s[i] == '(':\n",
    "                left += 1\n",
    "            else:\n",
    "                right += 1\n",
    "            if left < right:\n",
    "                left = 0\n",
    "                right = 0\n",
    "            elif left == right:\n",
    "                res = max(res, left + right)\n",
    "        left = 0\n",
    "        right = 0\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if s[i] == '(':\n",
    "                left += 1\n",
    "            else:\n",
    "                right += 1\n",
    "            if left > right:\n",
    "                left = 0\n",
    "                right = 0\n",
    "            elif left == right:\n",
    "                res = max(res, left + right)\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidParentheses(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [0 for _ in range(n)]\n",
    "        ans = 0\n",
    "        for i in range(1, n):\n",
    "            if s[i] == ')':\n",
    "                p = i - dp[i - 1] - 1\n",
    "                if p >= 0 and s[p] == '(':\n",
    "                    dp[i] = dp[i-1] + 2\n",
    "                    if p >= 1:\n",
    "                        dp[i] += dp[p-1]\n",
    "            ans = max(ans, dp[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidParentheses(self, s: str) -> int:\n",
    "        if s==\"\":\n",
    "            return 0\n",
    "        n = len(s)\n",
    "        dp = [0]*n\n",
    "        for i in range(n):\n",
    "            if s[i]==\"(\":\n",
    "                continue\n",
    "            else:\n",
    "                p = i-dp[i-1]-1\n",
    "                if p>=0 and s[p]==\"(\":\n",
    "                    dp[i] = dp[i-1]+2+dp[p-1] if p-1>=0 else dp[i-1]+2\n",
    "        return max(dp)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidParentheses(self, s: str) -> int:\n",
    "        stack=[] # 构建一个栈记录字符index\n",
    "        ans=0\n",
    "        for i in range(len(s)):\n",
    "            # 如果栈非空，且当前为右括号，且有记录的左括号，则出栈\n",
    "            if stack and s[i]==\")\" and s[stack[-1]]==\"(\":\n",
    "                stack.pop()\n",
    "                # 如果出栈后变成空栈，则说明整个[0:i]的区间都是合格的，长度为i+1\n",
    "                # 如果出栈后非空，则说明区间[stack[-1]:i]是合格的\n",
    "                ans=max(ans,i-(stack[-1] if stack else -1))\n",
    "            else:\n",
    "                # 以下3个条件会触发else\n",
    "                # 如果是空栈\n",
    "                # 或者当前字符为左括号（需要寻找匹配的右括号）\n",
    "                # 或者当前字符为右括号，而且栈顶记录的也是右括号（不合格的情况，永远不会被pop）\n",
    "                stack.append(i)\n",
    "                \n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidParentheses(self, s: str) -> int:\n",
    "        stack=[]\n",
    "        ans=0\n",
    "        n=len(s)\n",
    "        for i in range(n):\n",
    "            if stack and s[i]==')' and s[stack[-1]]=='(':\n",
    "                stack.pop()                \n",
    "                ans=max(ans,i-stack[-1] if stack else i+1)\n",
    "                \n",
    "            else:\n",
    "                stack.append(i)\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidParentheses(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        #\")()())\" #tmp用来括号检测, tmp_dex,也同步放入dex, 然后每次弹出.计算弹出匹配的长度即可.\n",
    "        tmp=[]\n",
    "        tmp_dex=[]\n",
    "        cnt=0\n",
    "        save=0\n",
    "        for dex,i in enumerate(s):\n",
    "            if i=='(':\n",
    "             tmp_dex.append(dex)\n",
    "             tmp.append('(')\n",
    "            if i==')' and len(tmp)>0 and tmp[-1]=='(':\n",
    "              aaa=tmp_dex.pop()\n",
    "              # save=max(save,dex-aaa+1)\n",
    "              if tmp_dex: #=======剩余有索引,算距离\n",
    "                 bbb=tmp_dex[-1]\n",
    "                 save=max(save,dex-bbb)\n",
    "              else: # 没有剩余, 就跟0做距离.\n",
    "                 save=max(save,dex-0+1)\n",
    "\n",
    "              tmp.pop()\n",
    "              continue\n",
    "            if i==')' and len(tmp)==0:\n",
    "              cnt=0\n",
    "              tmp.append(')')\n",
    "              tmp_dex.append(dex)\n",
    "              continue\n",
    "            if i==')'         and len(tmp)>0 and tmp[-1]!='(':  \n",
    "\n",
    "               tmp.append(')')\n",
    "               tmp_dex.append(dex)\n",
    "               continue\n",
    "        return save"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidParentheses(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        st=[]\n",
    "        for i in range(n):\n",
    "            if st and s[i]==\")\":\n",
    "                st.pop()\n",
    "            elif s[i]==\"(\":\n",
    "                st.append(i)\n",
    "        st2=[]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if st2 and s[i]==\"(\":\n",
    "                st2.pop()\n",
    "            elif s[i]==\")\":\n",
    "                st2.append(i)\n",
    "        stack=st+st2\n",
    "        stack.sort()\n",
    "        stack=[-1]+stack+[n]\n",
    "        lenstack=len(stack)\n",
    "        ans=0\n",
    "        for i in range(1,lenstack):\n",
    "            ans=max(stack[i]-stack[i-1]-1,ans)\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
